package code.homework;

import java.util.*;

public class FindLadders {


    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        Map<String , Set<String>> wordsDict = new HashMap<String,Set<String>>();

        for (int i = 0; i< wordList.size() ; i++ ) {

            for (int j = 1; j< wordList.size() ; j++ ) {
                if(isSimilar(wordList.get(i),wordList.get(j))) {
                    put(wordsDict, wordList.get(i), wordList.get(j));
                    put(wordsDict, wordList.get(j), wordList.get(i));
                }
            }

            if(isSimilar(wordList.get(i),beginWord)) {
                put(wordsDict, wordList.get(i), beginWord);
                put(wordsDict, beginWord, wordList.get(i));
            }
        }

        if(!wordsDict.containsKey(beginWord) && !wordsDict.containsKey(endWord)) {
            return Collections.emptyList();
        }

        Map<String , List<String>> paths = new HashMap<String,List<String>>();
        boolean isFound = bfs(wordsDict,paths,beginWord,endWord);
        List<List<String>> res= new ArrayList<List<String>>();
        Deque<String> deque = new LinkedList();
        if (isFound) {
            //WHITE未发现, GRAY 已发现正在探索, BLACK 探索完成
            deque.addLast(beginWord);
            dfs(beginWord, endWord,paths,res,deque);
        }
        /**
         * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
         * "hit" -> "hot" -> "lot" -> "log" -> "cog"
         *
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/word-ladder-ii
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         */
        return res;
    }

    static void dfs(String beginWord, String endWord, Map<String , List<String>> paths,List<List<String>> res,Deque<String> deque){
        if(beginWord.equals(endWord)){
            res.add(new ArrayList<>(deque));
        }
        for (String word : paths.get(beginWord)) {
            deque.addLast(word);
            dfs(word,endWord,paths,res,deque);
            deque.removeLast();
        }
    }


    static boolean bfs(Map<String , Set<String>> wordsDict,Map<String , List<String>> path,String beginWord, String endWord) {
        Queue<String> queue = new LinkedList<>();
        Map<String ,Integer > depthMap = new HashMap<>();
        queue.add(beginWord);
        depthMap.put(beginWord,0);
        boolean isFound = false;
        int maxDepth = 501;
        while(!queue.isEmpty()){
            String word = queue.poll();
            path.put(word,new ArrayList<>());
            Set<String> nexts = wordsDict.get(word);
            if(nexts != null) {
                int depth = depthMap.get(word) +1;
                if(depth > maxDepth) {
                    continue;
                }
                for (String next:nexts) {
                    if(!depthMap.containsKey(next) || depthMap.get(next) == depth){
                        queue.add(next);
                        depthMap.put(next,depth);
                        path.get(word).add(next);
                        if(next.equals(endWord)){
                            isFound = true;
                            maxDepth = depth;
                        }
                    }
                }

            }
        }
        return isFound;

    }






    static void put(Map<String,Set<String>> wordsDict, String key, String value ){
        if (wordsDict.containsKey(key)) {
            wordsDict.get(key).add(value);
        } else {
            Set<String> list = new TreeSet<>();
            list.add(value);
            wordsDict.put(key,list);
        }

    }


    static boolean isSimilar(String word1,String word2) {
        int count = 0;
        for (int i = 0 ; i < word1.length() ; i++ ) {
            if(word1.charAt(i) != word2.charAt(i)){
                count ++;
            }
            if(count >= 2 ){
                return false;
            }
        }
        if(count == 1){
            return true;
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        /**
         * 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
         * 输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
         * 解释：存在 2 种最短的转换序列：
         * "hit" -> "hot" -> "dot" -> "dog" -> "cog"
         * "hit" -> "hot" -> "lot" -> "log" -> "cog"
         *
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/word-ladder-ii
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         */
        List<String> words = Arrays.asList("hot","dot","dog","lot","log","cog");
        findLadders("hit", "cog",words);
    }


}
